package binarysearch;

public class Project34 {
    /**
     * 二分查找，查找target的左边界右边界
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        //存放结果
        int [] result = new int[2];
        //查找区间的左、右边界
        int left = 0;
        int right = nums.length - 1;
        int mid;

        //查找左边界
        while(left <= right) {
            mid = (left + right) / 2;

            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        if (left == nums.length || nums[left] != target) {
            result[0] = -1;
        } else {
            result[0] = left;
        }

        //查找右边界
        left = 0;
        right = nums.length - 1;

        //查找右边界
        while(left <= right) {
            mid = (left + right + 1) / 2;

            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }

        if (right == -1 || nums[right] != target ){
            result[1] = -1;
        }else {
            result[1] = right;
        }

        return result;
    }

    public static void main(String[] args) {
        int [] nums = new int[]{5,7,7,8,8,10};
        Project34 project34 = new Project34();
        int[] ints = project34.searchRange(nums, 8);

        for (int i : ints) {
            System.out.println("i = " + i);
        }

    }

}
